This invention relates in general to digital networks and more specifically to synchronizing packet transfers over a digital network.
Many of today's digital networks use packet transfers. Data to be transferred is separated into relatively small blocks called packets that including a header and other possible information. The packets are then sent over the network and reassembled. Due to signal and line noise, processing or transfer errors, equipment failure, interruptions, suspensions, routing changes, re-ordering operations or other events, packets can be received out-of-order or corrupted or even lost completely during transfer.
One approach provided by the prior art to improve packet transmission and reception is to include a “sequence number” as part of a packet's information. A sender, or sending device, includes a sequence number in each packet. A starting sequence number is agreed upon by the sender and receiver. Subsequent sequence numbers are typically incremented by one so that each packet has a sequence number that is incrementing in a series.
Such an approach is used, for example, in the Internet with Transmission Control Protocol (TCP) and in “core” or backbone transfers with Virtual Private Network (VPN) sequence numbers. Other protocols and networks also employ packets and sequence numbers. By comparing a received packet's sequence number with an expected sequence number (i.e., the next sequence number expected in the series) a receiver, or receiving device, has some ability to detect missing or out-of-sequence packets, and to reorder the packets or take other corrective measures to recover the entire data that was intended to be transferred.
The use of sequence numbers is not without limitations and shortcomings. In popular packet protocols the sequence number is typically limited to 16 bits to save space since the sequence number must be transmitted with every packet. The sequence number is represented as a positive integer so that the range of possible sequence numbers is 0 to 65535. Because of this, when a sequence number needs to be incremented past 65535, the sequence number is instead reset to 1 (the sequence number 0 is reserved). This effect is also called “wraparound”. Since a receiving device is aware of the wraparound condition this does not pose a problem to accurate use of the sequence numbers.
Another property of current sequence number approaches is that they usually are designed to handle cases where packets are received out of order. They should also permit a receiver to use portions of data where a short interruption causes some packets to be lost but where it is still desirable for the receiver to continue working with as much of the intended data as possible. Otherwise the receiver must make a new request for lost or interrupted data, or might have to cause a reset of the sender and/or receiver or other time-consuming exchange. For this reason, it is typically acceptable for sequence numbers to deviate substantially from strict adherence to the incrementing series and a packet with the deviating sequence number will still be considered valid, or accepted, and is said to have “passed” the sequence number test and be “in order.”
In VPN sequence numbers, for example, the deviation between the expected sequence number and an acceptable sequence number can vary by as much as 32768, or approximately half of the maximum number, 65535. One way to look at this is that the “window” of acceptable sequence numbers can be approximately one-half of the total range of possible sequence numbers. The rules for determining whether a packet is in-order are usually a bit more complex than a simple, single window. For example, an IETF draft referred to as “draft-ietf-pwe3-atm-encap-02” proposes the following sequence number checking algorithm for a received packet:                if the sequence number on the packet is 0, then the packet passes the sequence number check        otherwise if the packet sequence number>=the expected sequence number and the packet sequence number−the expected sequence number<32768, then the packet is in order.        otherwise if the packet sequence number<the expected sequence number and the expected sequence number−the packet sequence number>=32768, then the packet is in order.        otherwise the packet is out of order.        If a packet passes the sequence number check, or is in order then, it can be delivered immediately. If the packet is in order, then the expected sequence number should be set using the algorithm:        expected_sequence_number:=packet_sequence_number+1 mod 2**16        if (expected_sequence_number=0) then                    expected_sequence_number:=1;                        Packets which are received out of order MAY be dropped or reordered at the discretion of the receiver.        If a router PE2 does not support receive sequence number processing, then the sequence number field MAY be ignored.        
Although not stated in the above sequence number checking rules, if a packet's sequence number fails then the expected sequence number is not changed for the next packet.
In VPN applications the network transactions are typically transferred over core network components that provide high-bandwidth, real-time long distance transfers. In these applications a sender may have to restart sequence numbering during normal cases like High Availability (HA), user configuration change, etc. If a receiver is not notified about the restart of sequence numbering, many packets could be dropped by mistake. For example, if the receiver is expecting sequence number 1,000 on a next packet and the sender restarts sequence numbering from 1 then the subsequent 999 packets will be dropped.
A common approach to solve the above problem requires that the sender and receiver sync-up on a new starting sequence number by using so-called “out-of-band” communications such as by sending special packet or header information to notify a receiver that the sequence numbers need to be re-synchronized. For example, the receiver can indicate to the sender that data has been dropped and must be resent. The sender then acknowledges this request and begins transmitting with a starting sequence number of 1. However, in Layer2 VPN services, the sender and receiver can be thousands of miles away across one or more Internet backbones. The new sequence number sync-up can easily take so much time that a large number of packets can be dropped. For example, a 100 msec delay on an OC192 link can cause up to few million packets to be dropped on the receive side before the receiver re-syncs with sender.